﻿using System;
using System.Collections.Generic;
using System.Text;

namespace GTTSOfLibrary.Algorithm
{
    /// <summary>
    /// 二叉树泛型类
    /// </summary>
    /// <typeparam name="T">泛型参数（T从IComparable<T>继承）</typeparam>
    public class BinaryTree<T> : IDisposable
        where T : IComparable<T>
    {
        private List<BinaryTree<T>> perLists = null;
        private List<BinaryTree<T>> mdiLists = null;
        private List<BinaryTree<T>> lastLists = null;
        private List<BinaryTree<T>> wideList = null;

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <remarks>
        /// 定义二叉树的根节点
        /// </remarks>
        /// <param name="nodeValue">二叉树的根节点</param>
        public BinaryTree(T nodeValue)
        {
            this.nodeData = nodeValue;
            this.left = null;
            this.right = null;

            if (perLists == null)
            {
                perLists = new List<BinaryTree<T>>();
            }
            if (mdiLists == null)
            {
                mdiLists = new List<BinaryTree<T>>();
            }
            if (lastLists == null)
            {
                lastLists = new List<BinaryTree<T>>();
            }
            if (wideList == null)
            {
                wideList = new List<BinaryTree<T>>();
            }
        }

        /// <summary>
        /// 析构函数
        /// </summary>
        ~BinaryTree()
        {
            Dispose();
        }

        private T nodeData;
        /// <summary>
        /// 获取或设置树节点属性
        /// </summary>
        public T NodeData
        {
            get { return this.nodeData; }
            set { this.nodeData = value; }
        }

        private BinaryTree<T> left;
        /// <summary>
        /// 获取或设置左子树
        /// </summary>
        public BinaryTree<T> Left
        {
            get { return this.left; }
            set { this.left = value; }
        }

        private BinaryTree<T> right;
        /// <summary>
        /// 获取或设置右子树
        /// </summary>
        public BinaryTree<T> Right
        {
            get { return this.right; }
            set { this.right = value; }
        }

        /// <summary>
        /// 插入节点
        /// </summary>
        /// <remarks>
        /// 存储思想，凡是小于该结点值的数据全部都在该节点的左子树中，凡是大于该结点结点值的数据全部在该节点的右子树中
        /// </remarks>
        /// <param name="Value">要插入的节点</param>
        public void Insert(T Value)
        {
            T curNodeValue = this.NodeData;

            //如果大于新节点，插入左子树，否则插入右子树
            if (curNodeValue.CompareTo(Value) > 0)
            {
                if (this.Left == null)
                {
                    this.Left = new BinaryTree<T>(Value);
                }
                else
                {
                    this.Left.Insert(Value);
                }
            }
            else
            {
                if (this.Right == null)
                {
                    this.Right = new BinaryTree<T>(Value);
                }
                else
                {
                    this.Right.Insert(Value);
                }
            }
        }

        /// <summary>
        /// 前序遍历树
        /// </summary>
        /// <param name="root">要遍历树的根节点</param>
        /// <returns>遍历后的顺序列表</returns>
        public List<BinaryTree<T>> PreOrderTree(BinaryTree<T> root)
        {
            if (root != null)
            {
                perLists.Add(root);
                PreOrderTree(root.Left);
                PreOrderTree(root.Right);
            }
            return perLists;
        }


        /// <summary>
        /// 中序遍历：左子树，根节点，右子树可以实现顺序输出
        /// </summary>
        /// <param name="root"></param>
        public List<BinaryTree<T>> MidOrderTree(BinaryTree<T> root)
        {
            if (root != null)
            {
                MidOrderTree(root.Left);
                mdiLists.Add(root);
                MidOrderTree(root.Right);
            }
            return mdiLists;
        }
        /// <summary>
        /// 后序遍历：左子树，右子树，根节点
        /// </summary>
        /// <param name="root"></param>
        public List<BinaryTree<T>> LastOrderTree(BinaryTree<T> root)
        {
            if (root != null)
            {
                LastOrderTree(root.Left);
                LastOrderTree(root.Right);
                lastLists.Add(root);
            }
            return lastLists;
        }
        /// <summary>
        /// 逐层遍历：遍历思想是从根节点开始，访问一个节点然后将其左右子树的根节点依次放入链表中，然后删除该节点。
        /// 依次遍历直到链表中的元素数量为0即没有更下一层的节点出现时候为止。
        /// </summary>
        public List<BinaryTree<T>> WideOrderTree()
        {
            List<BinaryTree<T>> nodeList = new List<BinaryTree<T>>();
            nodeList.Add(this);
            BinaryTree<T> temp = null;
            while (nodeList.Count > 0)
            {
                wideList.Add(nodeList[0]);
                temp = nodeList[0];
                nodeList.Remove(nodeList[0]);
                if (temp.Left != null)
                {
                    nodeList.Add(temp.Left);
                }
                if (temp.Right != null)
                {
                    nodeList.Add(temp.Right);
                }
            }
            return wideList;
        }

        #region IDisposable 成员
        /// <summary>
        /// 释放资源
        /// <remarks>
        ///  继承IDisposable接口
        /// </remarks>
        /// </summary>
        public void Dispose()
        {
            if (perLists != null)
            {
                perLists.Clear();
            }
            if (mdiLists != null)
            {
                mdiLists.Clear();
            }
            if (lastLists != null)
            {
                lastLists.Clear();
            }
            if (wideList != null)
            {
                wideList.Clear();
            }
        }
        #endregion

        /// <summary>
        /// 重写Tostring方法
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            return string.Format(NodeData.ToString());
        }
    }
}
